package com.example.myletcodelearing.one

import java.lang.StringBuilder
import java.util.*
import kotlin.collections.ArrayList
import kotlin.collections.HashMap
import kotlin.math.abs


/**
 * @author tgw
 * @date 2022/11/7
 * https://leetcode.cn/problems/3sum/?favorite=2cktkvj
给你一个整数数组 nums ，判断是否存在三元组
[nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

 

 

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。


 */

fun main(args: Array<String>) {
    var op = Solution22.Solution()
    var num = arrayOf(-1,0,1,2,-1,-4)
    var result = op.threeSum4(num)


    print("打印：$result")


}

private class Solution22 {
    internal class Solution {
        fun threeSum(nums: Array<Int>): List<List<Int?>> {
            var i = 0
            var list = ArrayList<List<Int?>>()
            var listfu = ArrayList<Int?>()
            var map = HashMap<Int, ArrayList<NUM>>()
            while (i < nums.size) {
                if (map.containsKey(0 - nums[i])) {

                    if (check(nums, i, map, listfu)) {
                    } else {
                        if (check1(nums, i, map, listfu)
                        ) {

                            add(nums, i, map, list, listfu)
//                            child.add(nums[map.get(0 - nums[i])!!.preIndex])
//                            child.add(nums[map.get(0 - nums[i])!!.afterIndex])
//                            child.add(nums[i])
//                            listfu.addAll(child)
//                            list.add(child)
                        }

                    }
                }
                var j = i + 1
                while (j < nums.size) {
                    if (map.containsKey(nums[i] + nums[j])) {
                        var listMap = map.get(nums[i] + nums[j])
                        if (listMap != null) {
                            listMap.add(NUM(i, j))
                            map[nums[i] + nums[j]] = listMap
                        }
                    } else {
                        var listMap = ArrayList<NUM>()
                        listMap.add(NUM(i, j))
                        map[nums[i] + nums[j]] = listMap

                    }
                    j++
                }
                i++
            }
            return list
        }

        fun check(
            nums: Array<Int>,
            i: Int,
            map: HashMap<Int, ArrayList<NUM>>,
            listfu: ArrayList<Int?>
        ): Boolean {
            var check = false
            for (nm in map.get(0 - nums[i])!!) {
                if (listfu.contains(nums[nm!!.preIndex]) &&
                    listfu.contains(nums[nm!!.afterIndex]) &&
                    listfu.contains(nums[i])
                ) {
                    check = true
                    break
                }
            }
            return check
        }

        fun check1(
            nums: Array<Int>,
            i: Int,
            map: HashMap<Int, ArrayList<NUM>>,
            listfu: ArrayList<Int?>
        ): Boolean {
            var check = false
            for (nm in map.get(0 - nums[i])!!) {
                if (nm!!.preIndex != i &&
                    nm!!.afterIndex != i
                ) {
                    check = true
                    break
                }
            }
            return check
        }

        fun add(
            nums: Array<Int>,
            i: Int,
            map: HashMap<Int, ArrayList<NUM>>,
            list: ArrayList<List<Int?>>,
            listfu: ArrayList<Int?>
        ) {

            for (nm in map.get(0 - nums[i])!!) {
                var child = ArrayList<Int>()
                child.add(nums[nm!!.preIndex])
                child.add(nums[nm!!.afterIndex])
                child.add(nums[i])
                listfu.addAll(child)
                list.add(child)
            }

        }


        class NUM(var preIndex: Int, var afterIndex: Int) {

        }


        fun threeSum2(nums: Array<Int>): List<List<Int?>> {
            var i = 0
            var list = ArrayList<List<Int?>>()
            var listfu = ArrayList<Int?>()
            var map = HashMap<Int, NUM>()
            while (i < nums.size) {
                if (map.containsKey(0 - nums[i])) {
                    var child = ArrayList<Int>()
                    if (listfu.contains(nums[map.get(0 - nums[i])!!.preIndex]) &&
                        listfu.contains(nums[map.get(0 - nums[i])!!.afterIndex]) &&
                        listfu.contains(nums[i])
                    ) {
                    } else {
                        if (map.get(0 - nums[i])!!.preIndex != i &&
                            map.get(0 - nums[i])!!.afterIndex != i
                        ) {
                            child.add(nums[map.get(0 - nums[i])!!.preIndex])
                            child.add(nums[map.get(0 - nums[i])!!.afterIndex])
                            child.add(nums[i])
                            listfu.addAll(child)
                            list.add(child)
                        }

                    }
                }
                var j = i + 1
                while (j < nums.size) {
                    map[nums[i] + nums[j]] = NUM(i, j)
                    j++
                }
                i++
            }
            return list
        }


        fun threeSum3(nums: Array<Int>): List<List<Int?>> {
            var list = ArrayList<List<Int?>>()
            if (nums.size < 3) {
                return list
            }
            nums.sort()
            var left = 0
            var right = nums.size - 1


            while (left + 1 < right) {
                var middle = left

                while (middle < right) {

                    if (middle != right && middle != left && nums[left] + nums[right] + nums[middle] == 0) {
                        var value = ArrayList<Int>()
                        value.add(nums[left])
                        value.add(nums[middle])
                        value.add(nums[right])
                        list.add(value)
                    }
                    if (middle != left && nums[left] + nums[right] + nums[middle] < 0) {
                        left++
                        break
                    }
                    middle++
                }
                middle = right

                while (middle > left) {

                    if (middle != right && middle != left && nums[left] + nums[right] + nums[middle] == 0) {
                        var value = ArrayList<Int>()
                        value.add(nums[left])
                        value.add(nums[middle])
                        value.add(nums[right])
                        list.add(value)
                    }
                    if (middle != right && nums[left] + nums[right] + nums[middle] > 0) {
                        right--
                        break
                    }
                    middle--
                }
            }
            return list
        }

        fun threeSum4(nums: Array<Int>): List<List<Int?>> {
            var list = ArrayList<List<Int?>>()
            if (nums.size < 3) {
                return list
            }
            //都是基于排好序的情况
            nums.sort()

            for (middle in 0 until nums.size) {
                var left = middle + 1
                var right = nums.size - 1
                //防止上一个middle 与下一个middle同一个值，导致重复值的出现
                if (middle>0 && nums[middle] ==nums[middle-1]){
                    continue
                }
                var find= false
                while (left < right) {
                    if (nums[left] + nums[right] + nums[middle] < 0) {
                        left++
                    } else if (nums[left] + nums[right] + nums[middle] > 0) {
                        right--
                    } else if (middle != right && middle != left && nums[left] + nums[right] + nums[middle] == 0) {
                        //防止找到过一次符合条件的值后，上一个left 与当前left同一个值，导致重复值的出现
                        if (find && nums[left] ==nums[left-1]){
                            left++
                            continue
                        }
                        var value = ArrayList<Int>()
                        value.add(nums[left])
                        value.add(nums[middle])
                        value.add(nums[right])
                        list.add(value)
                        find = true
                        left++
                    }
                }
            }

            return list
        }


    }


}
